package _dp_base;

/**
 * 198. 打家劫舍
 */
public class No198 {
    private int[] nums;

    /**
     * 1. 递归
     */
    public int rob(int[] nums) {
        this.nums = nums;
        int n = nums.length;
        return dfs(n - 1);
    }

    private int dfs(int i) {
        if (i < 0) return 0;
        return Math.max(dfs(i - 1), dfs(i - 2) + nums[i]);
    }

    /**
     * 2. 迭代
     */
    public int rob2(int[] nums) {
        int n = nums.length;
        int[] f = new int[n + 2];
        for (int i = 0; i < n; i++) {
            f[i + 2] = Math.max(f[i + 1], f[i] + nums[i]);
        }
        return f[n + 1];
    }

    /**
     * 3. 空间优化
     */
    public int rob3(int[] nums) {
        int f0 = 0, f1 = 0;
        for (int num : nums) {
            int temp = f1;
            f1 = Math.max(f1, f0 + num);
            f0 = temp;
        }
        return f1;
    }
}
